package com.ai.zuochengyun.phase01.class06;

import java.util.*;

/**
 * 节点数越多，排序越靠前
 */
public class Code04_TopologicalOrderDFS1 {

    public static List<DirectedGraphNode> topSort(List<DirectedGraphNode> graph) {
        Map<DirectedGraphNode, Record> order = new HashMap<>();
        for (DirectedGraphNode cur : graph) {
            process(cur, order);
        }

        // 按频次排序
        List<Record> array = new ArrayList<>();
        for (Record record : order.values()) {
            array.add(record);
        }
        array.sort(new MyComparator());

        List<DirectedGraphNode> ans = new ArrayList<>();
        for (Record record : array) {
            ans.add(record.node);
        }
        return ans;
    }

    /**
     * 返回cur点所到之处的点的频次
     * @param cur 当前来到的点
     * @param order
     */
    private static Record process(DirectedGraphNode cur, Map<DirectedGraphNode, Record> order) {
        if (order.containsKey(cur)) {
            return order.get(cur);
        }

        int nodes = 0;
        for (DirectedGraphNode next : cur.neighbors) {
            nodes += process(next, order).nodes;
        }

        Record ans = new Record(cur, nodes);
        // 放进缓存
        order.put(cur, ans);
        return ans;
    }

    /**
     * 倒序排序
     */
    private static class MyComparator implements Comparator<Record> {

        @Override
        public int compare(Record o1, Record o2) {
            // 返回负数，第一个参数排前面，返回正数，第二个参数排前面
            return o2.nodes - o1.nodes;
        }
    }

    private static class Record {
        public DirectedGraphNode node;

        public int nodes;

        public Record(DirectedGraphNode node, int nodes) {
            this.node = node;
            this.nodes = nodes;
        }
    }
}
